﻿namespace AlgorithmInterview.Chapter04._01;

// 找出数组中唯一的重复元素
public class Test05
{
    /// <summary>
    /// 环形相遇法
    /// </summary>
    /// <param name="array"></param>
    /// <returns></returns>
    public int FindDup(int[] array)
    {
        if (array == null)
            return -1;
        int len = array.Length;
        int slow = 0;
        int fast = 0;
        do
        {
            fast = array[array[fast]];
            slow = array[slow];
        } while (slow != fast);

        fast = 0;
        do
        {
            fast = array[fast];
            slow = array[slow];
        } while (slow != fast);

        return slow;
    }
}